﻿// 140. 单词拆分 II.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_set>


using namespace std;
/*
https://leetcode.cn/problems/word-break-ii/
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。
以任意顺序 返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：
输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]

示例 2：
输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。

示例 3：
输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]


提示：
1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都 不同
*/


class Solution {
public:
    vector<string> ans;
    string curr;

    bool dfs(const string& s, const unordered_set<string> sset, int l, int r) {
        if (l > r) {
            curr.pop_back();
            ans.push_back(curr);
            return 1;
        }
        
        for (int i = l; i <= r; i++) {
            string sub = s.substr(l, i - l + 1);
            if (sset.count(sub) != 0) {
                string old = curr;
                curr += sub; curr += " ";
                dfs(s, sset, i + 1, r);
                curr = old;
            }
        }

        return 0;
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> sset;
        for (auto& e : wordDict) { sset.insert(e); }

        dfs(s, sset, 0, s.size()-1);

        return ans;
    }
};

int main()
{
    Solution s;
    string v = "catsanddog";

    vector<string> w{
        "cat","cats","and","sand","dog"
    };

    s.wordBreak(v,w);
}

 